package 力扣.堆;

import org.omg.CORBA.INTERNAL;

import java.util.Comparator;
import java.util.PriorityQueue;

public class 最低加油次数871 {
    public static void main(String[] args) {
        int target = 100;
        int startFuel = 50;
//        int[][] stations = {{10,60},{20,30},{30,30},{60,40}};
//        int[][] stations = {{25,25},{50,25},{75,25}};
//        int[][] stations = {{13,21},{26,115},{100,47},{225,99},{299,141},{444,198},{608,190},{636,157},{647,255},{841,123}};
//        int[][] stations = {{10,10},{10,200}};
//        int[][] stations = {{25,30}};
        int[][] stations = {{50,50}};
//        int[][] stations = {{10,60},{20,30},{30,30},{60,40}};
        int i = minRefuelStops(target, startFuel, stations);
        System.out.println(i);
    }

    /**
     * 消耗问题：将消耗过程转为收集过程
     * 汽车为什么需要加油？：当前油箱中的油不够到达下一个（加油站/目的地）
     * 将加油站中的油放在后备箱中作为备用油（收集过程），每次需要加油的时候，从中选择一个最多的油加上（大根堆）。
     * @return
     */
    public static int minRefuelStops(int target, int startFuel, int[][] stations) {
        int ans = 0;
        if (startFuel >= target){//初始边界条件
            return 0;
        }
        PriorityQueue<Integer[]> pq = new PriorityQueue<Integer[]>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o2[1] - o1[1];//大根堆
            }
        });
        int teMax = startFuel;//当前汽车油箱的油量
        int pe = 0;//已经走过的路程

        int i = 0;
        while (i < stations.length || !pq.isEmpty()){//还有加油站或者后备箱里面还有备用油可加
            while (i < stations.length &&(teMax - (stations[i][0]- pe) ) >=0){
                    pq.offer(new Integer[]{stations[i][0],stations[i][1]});
                    i++;
            }
            //此时，两种情况：1、当前油箱的油量 已经不够到达下一个加油站了，2、已经走完了所有加油站

            if (teMax >= (target - pe) ){//判断是否能够到达终点
                return ans;
            }
            if (!pq.isEmpty()){//还有备用油
                 Integer[] te= pq.poll();//选择最多的
                 teMax -= (te[0] - pe);
                 teMax += te[1];
                 pe = te[0];
                 ans++;
            }else {
                    //没有了备用油，也到不了终点
                    return -1;
            }

        }

        return teMax >= (target- pe) ? ans : -1;
    }
}
